package cn.yuemouren.toflashback;

import java.util.LinkedList;
import java.util.List;

/**
 * <p>
 * N皇后问题 -> 运用回溯算法
 * <p>
 * 时间复杂度是 n的n！
 * </p>
 *
 * @author Timi
 * @date 2021/5/11 上午10:06
 **/
public class NqueenProblem {

    private List<List<LinkedList<String>>> result;

    public NqueenProblem() {
        this.result = new LinkedList<>();
    }

    /**
     * n个皇后站位问题
     *
     * @param n 皇后数量
     *
     * @return 返回所有皇后站位情况
     */
    public List<List<LinkedList<String>>> solveNQueens(int n) {
        LinkedList<LinkedList<String>> track = new LinkedList<>();
        //初始化构建
        buildQueue(track, n);
        backTracking(n, 0, track);
        return result;
    }

    /**
     * 利用回溯算法
     *
     * @param n     皇后数量
     * @param row   从哪行开始
     * @param track 用于保存一次站位问题
     */
    private void backTracking(int n, int row, LinkedList<LinkedList<String>> track) {
        //一次站位结束条件
        if (row == track.size()) {
            //值需要深拷贝
            result.add(track);
            return;
        }

        for (int col = 0; col < n; col++) {
            if (!isValid(row, col, track)) {
                continue;
            }
            //放置皇后
            track.get(row).set(col, "Q");
            //设置下一行
            backTracking(n, row + 1, track);
            //重置皇后
            track.get(row).set(col, ".");
        }
    }

    /**
     * 校验是否能放置皇后
     *
     * @param row   行
     * @param col   列
     * @param track 放置皇后情况数组
     *
     * @return 返回true 可以放置，false 不可以放置
     */
    private boolean isValid(int row, int col, LinkedList<LinkedList<String>> track) {

        int n = track.size();
        //同一列上
        for (int i = 0; i < n; i++) {
            String s = track.get(i).get(col);
            if ("Q".equals(s)) {
                return false;
            }
        }

        //左上角
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            String s = track.get(i).get(j);
            if ("Q".equals(s)) {
                return false;
            }
        }

        //右上角
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            String s = track.get(i).get(j);
            if ("Q".equals(s)) {
                return false;
            }
        }
        return true;
    }

    /**
     * 构建初始化矩阵
     *
     * @param result
     */
    private void buildQueue(LinkedList<LinkedList<String>> result, int n) {
        for (int i = 0; i < n; i++) {
            LinkedList<String> temp = new LinkedList<>();
            for (int j = 0; j < n; j++) {
                temp.add(".");
            }
            result.add(temp);
        }
    }

    public static void main(String[] args) {
        /*NqueenProblem np = new NqueenProblem();
        List<List<LinkedList<String>>> lists = np.solveNQueens(4);
        System.out.println(lists.size());
        System.out.println(lists);*/
        int size = 8;
        if((size & 1) == 0){
            System.out.println(1);
        }
    }
}
